package leetcode.D100.T22;

import java.util.*;

class Solution {
    /*// 解法一：dfs
    public List<String> generateParenthesis(int n) {
        List<String> result = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        dfs(result, sb, n, n);
        return result;
    }
    private void dfs(List<String> result, StringBuilder sb, int left, int right) {
        if(left == 0 && right == 0) {
            result.add(sb.toString());
            return;
        }
        // 向左衍生
        if(left > 0) {
            sb.append('(');
            dfs(result, sb, left-1, right);
            sb.deleteCharAt(sb.length()-1);
        }
        // 向右衍生
        if(right > left) {
            sb.append(')');
            dfs(result, sb, left, right-1);
            sb.deleteCharAt(sb.length()-1);
        }
    }*/
    // 解法二：bfs
    /*class Node {
        String res;
        int left;
        int right;

        public Node(String res, int left, int right) {
            this.res = res;
            this.left = left;
            this.right = right;
        }
    }
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        if(n == 0) return result;
        Deque<Node> dq = new LinkedList<>();
        dq.addLast(new Node("", n, n));
        while(!dq.isEmpty()) {
            int size = dq.size();
            for(int i=0; i<size; ++i) {
                Node front = dq.removeFirst();
                if(front.left == 0 && front.right == 0) {
                    result.add(front.res);
                    continue;
                }
                if(front.left > 0) {
                    dq.addLast(new Node(front.res + "(", front.left-1, front.right));
                }
                if(front.right > front.left) {
                    dq.addLast(new Node(front.res + ")", front.left, front.right-1));
                }
            }
        }
        return result;
    }*/

    // 解法三：迭代（动态规划）
    /*public List<String> generateParenthesis(int n) {
        List<String>[] temps = new List[n+1];
        temps[0] = new ArrayList<>();
        temps[1] = new ArrayList<>();
        temps[1].add("()");
        StringBuilder sb = new StringBuilder();
        sb.append('(');
        for(int i=2; i<=n; ++i) {
            List<String> temp = new ArrayList<>();
            for(int j=0; j<=i-1; ++j) {
                List<String> left = temps[j];
                List<String> right = temps[i-1-j];
                if(left.size() == 0) {
                    sb.append(')');
                    help(temp, sb, false, right);
                    sb.deleteCharAt(sb.length()-1);
                } else if(right.size() == 0) {
                    help(temp, sb, true, left);
                } else {
                    for(int k=0; k<left.size(); ++k) {
                        String s1 = left.get(k);
                        sb.append(s1);
                        sb.append(')');
                        for(int m=0; m<right.size(); ++m) {
                            String s2 = right.get(m);
                            sb.append(s2);
                            temp.add(sb.toString());
                            sb.delete(sb.length()-s2.length(), sb.length());
                        }
                        sb.delete(sb.length()-s1.length()-1, sb.length());
                    }
                }
            }
            temps[i] = temp;
        }
        return temps[n];
    }

    private void help(List<String> temp, StringBuilder sb, boolean flag, List<String> ss) { // true表示要自己加上)
        for(int i=0; i<ss.size(); ++i) {
            String s = ss.get(i);
            sb.append(s);
            if(flag) {
                sb.append(')');
            }
            temp.add(sb.toString());
            if(flag) {
                sb.delete(sb.length()-s.length()-1, sb.length());
            } else {
                sb.delete(sb.length()-s.length(), sb.length());
            }
        }
    }*/

    // 二刷：dfs最简单
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        dfs(result, sb, 0, 0, n);
        return result;
    }

    private void dfs(List<String> result, StringBuilder sb, int left, int right, int n) {
        if (right == n) {
            result.add(sb.toString());
            return;
        }
        if (left < n) {
            sb.append('(');
            dfs(result, sb, left+1, right, n);
            sb.deleteCharAt(sb.length()-1);
        }
        if (left > right) {
            sb.append(')');
            dfs(result, sb, left, right+1, n);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}
